The invention relates to devices for computing cosine transforms, which are used more particularly for image coding so as to reduce the amount of information representing these images. Such information reduction allows images to be transmitted or stored using means having a limited information rate.
It is known to code values representative of the luminance and of the color of the pixels of an image by a transformation called bi-dimensional cosine transformation which causes a matrix of N.times.N values, called direct cosine transforms, to correspond to a matrix of N.times.N values representative of a block of N.times.N pixels of the image to be coded. This image is generally divided up into square portions each formed of a block of N.times.N pixels. Weighting of the transformed values reduces the amount of information representative of an image. Decoding consists in applying reverse weighting then a reverse cosine transformation which causes a matrix of N.times.N reverse transform values to correspond to a matrix of N.times.N direct transforms. Like coding, decoding is carried out by blocks of N.times.N image pixels.
If the values representative of the pixels of a block are f(i, j) for i=0 to N-1 and j=0 to N-1, the values of the bidimensional direct cosine transforms are given by the following formulae:
for u=0 to N-1 PA1 and v=0 to N-1 ##EQU1## with c(u)=1.sqroot.2 for u=0 and c(v)=1.sqroot.2 for v=0 and c(u)=1 for u=1 and c(v)=1 for v=1,2, . . . ,N-1 and with ##EQU2## PA1 c(k)=1 for k=1,2, . . . ,N-1 PA1 and ##EQU5##
The reverse transformed values are given by the bi-dimensional reverse cosine transformation by applying the following formula: ##EQU3##
This bi-dimensional cosine transformation may be broken down into two mono-dimensional cosine transformations and the bi-dimensional transforms may be computed using two mono-dimensional transform computing devices connected together in cascade.
The mono-dimensional cosine transformation is carried out in accordance with the following formulae: for k=0,1,2, . . . ,N-1 ##EQU4## with c(k)=1.sqroot.2 for k=0
The mono-dimensional reverse cosine transformation is carried out using the following formulae: ##EQU6##
The coding of an image by cosine transformation followed by weighting, greatly reduces the amount of information to be transmitted but has the drawback of requiring very numerous computations. This amount of computations is costly in equipment and in computation time. It makes it very difficult to apply the cosine transformation to coding and decoding a succession of video images at the usual frequency, 50 frames per second in the European standards.
High speed algorithms are known for carrying out a cosine transformation with a relatively reduced number of elementary multiplications and additions, particularly the algorithm of Chen et al which is described more particularly by R. A. Duryea in the article entitled "Performance of a source/channel encoded imagery transmission system" Thesis AFIT/GE/EE/79D-12, Air Force Institute of Technology, OHIO December 1979. It is derived from the above formula (3) using the mathematical relationships existing between the coefficients a.sub.ik. With this algorithm, a mono-dimensional cosine transformation of the numerical values representative of 16 pixels may be carried out using 44 multiplications and 74 additions. It has been used in mono-dimensional cosine transform computing devices but this algorithm has the drawback of having an irregular structure resulting in a certain complexity of the implementation device.
The aim of the invention is to provide, for a low cost, a device for computing mono-dimensional direct cosine transforms and a device for computing mono-dimensional reverse cosine transforms having a simpler structure than the devices using the algorithm of Chen et al, for transforming successions of 16 values. The aim of the present invention is also to provide a coding device and a decoding device applying in real time the bi-dimensional cosine transformation to video images complying with conventional television standards.
The invention provides particularly a device for computing mono-dimensional direct cosine transforms and a device for computing mono-dimensional reverse cosine transforms, using two algorithms derived from known algorithms, described by Beyeong Gi Lee in "A new algorithm to compute the discrete cosine transform"--IEEE Trans. on Acoustic, Speech and Signal Processing. Vol. ASSP-32, n.6, pp1243-1245, December 1984. These algorithms of Beyeong Gi Lee are modified so that they can be used by transform computation devices formed essentially of a small number of ROMs and a small number of elementary computation devices formed by commercially available integrated circuits, and able to operate at a rate equal to the rate of analysis of the pixels in conventional television standards.
The invention also provides a device for coding and a device for decoding images by bi-dimensional cosine transformation, including two mono-dimensional cosine transform computing devices.